{
 "nbformat": 4,
 "nbformat_minor": 2,
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "version": "3.8.1-final"
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3,
  "kernelspec": {
   "name": "python38164bitbed07143d37b49c8ba24bbf4d83c1753",
   "display_name": "Python 3.8.1 64-bit"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "5. 最长回文子串\n",
    "给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。\n",
    "\n",
    "示例 1：\n",
    "\n",
    "输入: \"babad\"\n",
    "输出: \"bab\"\n",
    "注意: \"aba\" 也是一个有效答案。\n",
    "示例 2：\n",
    "\n",
    "输入: \"cbbd\"\n",
    "输出: \"bb\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 暴力破解"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    \"\"\"\n",
    "    循环出所有的可能性，判断是不是回文\n",
    "    结果：完美超时\n",
    "    \"\"\"\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        if not s:\n",
    "            return \"\"\n",
    "        def is_palindrome(string: str):\n",
    "            return string == string[::-1]\n",
    "        n = len(s)\n",
    "        palindrome = s[0]\n",
    "        for i in range(n):\n",
    "            for j in range(i+2, n+1):\n",
    "                # print(s[i:j], i,j)\n",
    "                if is_palindrome(s[i:j]):\n",
    "                    if len(palindrome) < j - i:\n",
    "                        palindrome = s[i:j]\n",
    "        return palindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "看了官方的题解 ： 我们首先初始化一字母和二字母的回文，然后找到所有三字母回文，并依此类推…"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$dp[i][j] = dp[i+1][j-1] and S_i == S_j$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    \"\"\"\n",
    "    动态规划\n",
    "    \"\"\"\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        if not s:\n",
    "            return \"\"\n",
    "        n = len(s)\n",
    "        dp = [[0]* n for i in range(n)]\n",
    "        # 初始化长度为1的\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "        \n",
    "        def is_palindrome(string: str):\n",
    "            return string == string[::-1]\n",
    "        max_palindrome = s[0]\n",
    "        # 初始化长度为2的\n",
    "        for i in range(n-1):\n",
    "            if is_palindrome(s[i:i+2]):\n",
    "                dp[i][i+1] = 1\n",
    "                max_palindrome = s[i:i+2]\n",
    "        \n",
    "        for i in range(3, n+1): # 循环长度\n",
    "            for j in range(0, n-i+1): \n",
    "                if dp[j+1][j+i-2] and s[j] == s[j+i-1]:\n",
    "                    # print(j ,j+i, s[j:j+i])\n",
    "                    if len(max_palindrome) < i: # 如果长度小与现在这个回文的长度，就重新赋值\n",
    "                        max_palindrome = s[j:j+i]\n",
    "                    dp[j][j+i-1] = 1\n",
    "                \n",
    "        return max_palindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "执行用时 :\n",
    "4700 ms\n",
    ", 在所有 Python3 提交中击败了\n",
    "26.32%\n",
    "的用户\n",
    "内存消耗 :\n",
    "21 MB\n",
    ", 在所有 Python3 提交中击败了\n",
    "20.96%\n",
    "的用户"
   ]
  }
 ]
}